package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-24 20:41
 */
public class SurroundingArea {

    public void solve(char[][] board) {
        int m = board.length;
        if (m == 0) return;
        m = board.length;
        int n = board[0].length;
        UF uf = new UF(m * n + 1);
        int dummy = m * n;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                uf.union(i * n, dummy);
            }
            if (board[i][n - 1] == 'O') {
                uf.union(i * n + n - 1, dummy);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                uf.union(i, dummy);
            }
            if (board[m - 1][i] == 'O') {
                uf.union((m - 1) * n + i, dummy);
            }
        }
        int[][] dp = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O') {
                    int k = 3;
                    while (k >= 0) {
                        int x = dp[k][0] + i;
                        int y = dp[k][1] + j;
                        if (board[x][y]=='O')
                        uf.union(x * n + y, i * n + j);
                        k--;
                    }
                }
            }
        }

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (!uf.connected(dummy, i * n + j))
                board[i][j] = 'X';
            }
        }


    }
}
